The process of rendering two-dimensional images from three-dimensional scenes is commonly referred to as image processing. As the modern computer industry evolves image processing evolves as well. One particular goal in the evolution of image processing is to make two-dimensional simulations or renditions of three-dimensional scenes as realistic as possible.
In addition, image processing is often used in connection with modeling or simulating real world scenarios where virtual or simulated objects representing physical, real world objects interact with one another in the simulated scenes. Video games, for example, are increasingly capable of depicting more and more realistic virtual environments, be it through the flight of a golf ball, the real world performance characteristics of a race car, the flight of an aircraft or the result of an explosion in a warfare game. In other commercial and scientific applications of image processing, e.g., flight simulation, ballistics simulation, etc., accurate modeling of the interactions of objects in a virtual environment is an even greater concern.
In many modern data processing systems, the modeling of the real world interaction of objects is handled by computer software commonly referred to as a physics engine. A physics engine attempts to simulate physical phenomena though the use of rigid body dynamics, soft body dynamics and/or fluid dynamics principles. A key component of most physics engines is a collision detection/collision response system, which seeks to detect when objects in a virtual environment collide with one another. Based upon detected collisions, dynamics simulation is typically performed to resolve the forces and motions applied to the objects subsequent to the collisions.
Some physics engines also rely on impulse-based algorithms, where impulses are applied between objects to propagate forces therebetween. When rigid or deformable bodies are in contact with one another, for example, forces applied to one body typically must be applied to the other bodies that are in contact with that body. Similarly, forces applied to fluids, fabrics and other highly deformable entities must typically be propagated through those entities.
While some higher precision physics engines are not constrained by time, many others, particularly those used in interactive video gaming applications, are required to operate in “real time.” Consequently, the operations performed in connection with physics calculations, e.g., collision detection and impulse propagation, often need to be completed quickly and efficiently.
Conventional collision detection and impulse propagation techniques typically operate in a serial, single threaded application were each object in motion is tested against all other objects in the scene, and impulses are propagated one by one between objects. In some instances, collision detection may utilize spatial culling to reduce the number of required collision calculations. Furthermore, objects may be modeled using level of detail (LOD) models to simplify objects down to more easily calculable shapes for the purpose of detecting when two objects come in contact. For example, many collision detection techniques use simple shapes such as spheres and other cubic volumes to represent more complex objects. More detailed bounding volumes can be devised in some applications to increase collision precision, however, doing so usually comes at the expense of more processing time and/or hardware requirements.
With continued improvements in semiconductor technology in terms of clock speed and increased use of parallelism, the capabilities of real time physics engines will inevitably increase. At the chip level, multiple processor cores are often disposed on the same chip, functioning in much the same manner as separate processor chips, or to some extent, as completely separate computers. In addition, even within cores, parallelism is employed through the use of multiple execution units that are specialized to handle certain types of operations. Hardware-based pipelining is also employed in many instances so that certain operations that may take multiple clock cycles to perform are broken up into stages, enabling other operations to be started prior to completion of earlier operations. Multithreading is also employed to enable multiple instruction streams to be processed in parallel, enabling more overall work to performed in any given clock cycle.
However, even with increased clock speed and parallelization, conventional collision detection and impulse propagation techniques still present bottlenecks to performance in most conventional architectures. In particular, conventional techniques often require large numbers of random memory accesses in order to retrieve and manage objects in a scene, which has been found to cause low cache utilization and other performance related bottlenecks.
Furthermore, distributing the workload among multiple parallel threads of execution can be problematic in many dynamic, real-time environments. In particular, the number of objects, and the distribution of those objects, within a given scene, can vary over time. Whereas at one point in time collisions between multiple objects, requiring substantial processing resources, may occur in one region of a scene, at a different time more extensive collisions, and thus, heavier processing workload, may occur in other regions of the scene.
A need therefore continues to exist in the art for a manner of efficiently handing physics collision detection and impulse propagation in a physics engine.